SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Matroid representation</title>

</head>

Matroid representation

</h1>

</header>

In the mathematical theory of <a href="Matroid" title="Matroid">matroids</a>, a matroid representation is a family of <a href="Vector_space" title="Vector space">vectors</a> whose <a href="Linear_independence" title="Linear independence">linear independence</a> relation is the same as that of a given matroid. Matroid representations are analogous to <a href="Group_representation" title="Group representation">group representations</a>; both types of representation provide abstract algebraic structures (matroids and groups respectively) with concrete descriptions in terms of <a href="Linear_algebra" title="Linear algebra">linear algebra</a>.

A linear matroid is a matroid that has a representation, and an F-linear matroid (for a <a href="Field_(mathematics)" title="Field (mathematics)">field</a> F) is a matroid that has a representation using a <a href="Vector_space" title="Vector space">vector space</a> over F. Matroid representation theory studies the existence of representations and the properties of linear matroids.

<div class="mw-heading mw-heading2"><h2 id="Definitions">Definitions</h2></div>

A (finite) <a href="Matroid" title="Matroid">matroid</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (E,{\mathcal {I}})}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (E,{\mathcal {I}})}</annotation>

</semantics>

</math><img src="./926cadcc73c8a5f0086993832f965b0c503ec018.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.111ex; height:2.843ex;" alt="{\displaystyle (E,{\mathcal {I}})}" loading="lazy"> is defined by a <a href="Finite_set" title="Finite set">finite set</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> (the elements of the matroid) and a non-empty <a href="Family_of_sets" title="Family of sets">family</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> of the subsets of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy">, called the independent sets of the matroid. It is required to satisfy the properties that every subset of an independent set is itself independent, and that if one independent set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> is larger than a second independent set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in A\setminus B}</annotation>

</semantics>

</math><img src="./7b4fd391edd6f4ef1b902715c9b4a80ea1b706f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.872ex; height:2.843ex;" alt="{\displaystyle x\in A\setminus B}" loading="lazy"> that can be added to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> to form a larger independent set. One of the key motivating examples in the formulation of matroids was the notion of <a href="Linear_independence" title="Linear independence">linear independence</a> of vectors in a <a href="Vector_space" title="Vector space">vector space</a>: if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> is a finite set or multiset of vectors, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {I}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {I}}}</annotation>

</semantics>

</math><img src="./0e9730a0ada0426927ff64141eb9f505eca132d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; margin-left: -0.069ex; width:1.561ex; height:2.176ex;" alt="{\displaystyle {\mathcal {I}}}" loading="lazy"> is the family of linearly independent subsets of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy">, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (E,{\mathcal {I}})}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (E,{\mathcal {I}})}</annotation>

</semantics>

</math><img src="./926cadcc73c8a5f0086993832f965b0c503ec018.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.111ex; height:2.843ex;" alt="{\displaystyle (E,{\mathcal {I}})}" loading="lazy"> is a matroid.<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a>

More generally, if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (E,{\mathcal {I}})}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (E,{\mathcal {I}})}</annotation>

</semantics>

</math><img src="./926cadcc73c8a5f0086993832f965b0c503ec018.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.111ex; height:2.843ex;" alt="{\displaystyle (E,{\mathcal {I}})}" loading="lazy"> is any matroid, then a representation of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (E,{\mathcal {I}})}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (E,{\mathcal {I}})}</annotation>

</semantics>

</math><img src="./926cadcc73c8a5f0086993832f965b0c503ec018.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.111ex; height:2.843ex;" alt="{\displaystyle (E,{\mathcal {I}})}" loading="lazy"> may be defined as a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> to a vector space <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> is independent if and only if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f|_{A}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f|_{A}}</annotation>

</semantics>

</math><img src="./717abad132f2fe4244a97fda2a6fdbebd803aa13.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.39ex; height:2.843ex;" alt="{\displaystyle f|_{A}}" loading="lazy"> is injective and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(A)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(A)}</annotation>

</semantics>

</math><img src="./2711c647e5397c7016ee21bbcea53565480bd5e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.831ex; height:2.843ex;" alt="{\displaystyle f(A)}" loading="lazy"> is linearly independent. A matroid with a representation is called a linear matroid, and if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V}</annotation>

</semantics>

</math><img src="./af0f6064540e84211d0ffe4dac72098adfa52845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.787ex; height:2.176ex;" alt="{\displaystyle V}" loading="lazy"> is a vector space over field F then the matroid is called an F-linear matroid. Thus, the linear matroids are exactly the matroids that are <a href="Isomorphism" title="Isomorphism">isomorphic</a> to the matroids defined from sets or multisets of vectors. The function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> will be <a href="Bijection" title="Bijection">one-to-one</a> if and only if the underlying matroid is simple (having no two-element dependent sets). Matroid representations may also be described more concretely using <a href="Matrix_(mathematics)" title="Matrix (mathematics)">matrices</a> over a field F, with one column per matroid element and with a set of elements being independent in the matroid if and only if the corresponding set of matrix columns is linearly independent. The <a href="Matroid_rank" title="Matroid rank">rank function</a> of a linear matroid is given by the <a href="Rank_(linear_algebra)" title="Rank (linear algebra)">matrix rank</a> of submatrices of this matrix, or equivalently by the <a href="Dimension_(vector_space)" title="Dimension (vector space)">dimension</a> of the <a href="Linear_span" title="Linear span">linear span</a> of subsets of vectors.<a href="#cite_note-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Characterization_of_linear_matroids">Characterization of linear matroids</h2></div>

Not every matroid is linear; the eight-element <a href="V%C3%A1mos_matroid" title="Vámos matroid">Vámos matroid</a> is one of the smallest matroids that is unrepresentable over all fields.<a href="#cite_note-4">[4]</a> If a matroid is linear, it may be representable over some but not all fields.

For instance, the nine-element rank-three matroid defined by the <a href="Perles_configuration" title="Perles configuration">Perles configuration</a> is representable over the <a href="Real_number" title="Real number">real numbers</a> but not over the <a href="Rational_number" title="Rational number">rational numbers</a>.

<a href="Binary_matroid" title="Binary matroid">Binary matroids</a> are the matroids that can be represented over the <a href="Finite_field" title="Finite field">finite field</a> <a href="GF(2)" title="GF(2)">GF(2)</a>; they are exactly the matroids that do not have the <a href="Uniform_matroid" title="Uniform matroid">uniform matroid</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U{}_{4}^{2}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U{}_{4}^{2}}</annotation>

</semantics>

</math><img src="./031fa5a80577fefddf2dfe13e7120aae5378c439.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.837ex; height:3.176ex;" alt="{\displaystyle U{}_{4}^{2}}" loading="lazy"> as a <a href="Matroid_minor" title="Matroid minor">minor</a>.<a href="#cite_note-tutte58-5">[5]</a> The unimodular or <a href="Regular_matroid" title="Regular matroid">regular matroids</a> are the matroids that can be represented over all fields;<a href="#cite_note-Wh872-6">[6]</a> they can be characterized as the matroids that have none of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U{}_{4}^{2}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U{}_{4}^{2}}</annotation>

</semantics>

</math><img src="./031fa5a80577fefddf2dfe13e7120aae5378c439.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.837ex; height:3.176ex;" alt="{\displaystyle U{}_{4}^{2}}" loading="lazy">, the <a href="Fano_plane" title="Fano plane">Fano plane</a> (a binary matroid with seven elements), or the <a href="Dual_matroid" title="Dual matroid">dual matroid</a> of the Fano plane as minors.<a href="#cite_note-tutte58-5">[5]</a><a href="#cite_note-Wh8712-7">[7]</a> Alternatively, a matroid is regular if and only if it can be represented by a <a href="Totally_unimodular_matrix" class="mw-redirect" title="Totally unimodular matrix">totally unimodular matrix</a>.<a href="#cite_note-tutte65-8">[8]</a>

<a href="Rota's_conjecture" title="Rota's conjecture">Rota's conjecture</a> states that, for every finite field F, the F-linear matroids can be characterized by a finite set of forbidden minors, similar to the characterizations described above for the binary and regular matroids.<a href="#cite_note-9">[9]</a> As of 2012, it has been proven only for fields of four or fewer elements.<a href="#cite_note-tutte58-5">[5]</a><a href="#cite_note-10">[10]</a><a href="#cite_note-s79-11">[11]</a><a href="#cite_note-12">[12]</a> For infinite fields (such as the field of the <a href="Real_number" title="Real number">real numbers</a>) no such characterization is possible.<a href="#cite_note-13">[13]</a>

<div class="mw-heading mw-heading2"><h2 id="Field_of_definition">Field of definition</h2></div>

For every <a href="Algebraic_number_field" title="Algebraic number field">algebraic number field</a> and every <a href="Finite_field" title="Finite field">finite field</a> F there is a matroid M for which F is the minimal subfield of its algebraic closure over which M can be represented: M can be taken to be of rank 3.<a href="#cite_note-Wh8718-14">[14]</a>

<div class="mw-heading mw-heading2"><h2 id="Characteristic_set">Characteristic set</h2></div>

The characteristic set of a linear matroid is defined as the set of <a href="Characteristic_(algebra)" title="Characteristic (algebra)">characteristics</a> of the fields over which it is linear.<a href="#cite_note-Ing71-15">[15]</a> For every <a href="Prime_number" title="Prime number">prime number</a> p there exist infinitely many matroids whose characteristic set is the singleton set {p},<a href="#cite_note-16">[16]</a> and for every <a href="Finite_set" title="Finite set">finite set</a> of prime numbers there exists a matroid whose characteristic set is the given finite set.<a href="#cite_note-17">[17]</a>

If the characteristic set of a matroid is infinite, it contains zero; and if it contains zero then it contains all but finitely many primes.<a href="#cite_note-Ox225-18">[18]</a> Hence the only possible characteristic sets are finite sets not containing zero, and cofinite sets containing zero.<a href="#cite_note-Ox226-19">[19]</a> Indeed, all such sets do occur.<a href="#cite_note-Ox228-20">[20]</a>

<div class="mw-heading mw-heading2"><h2 id="Related_classes_of_matroids">Related classes of matroids</h2></div>

A <a href="Uniform_matroid" title="Uniform matroid">uniform matroid</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U{}_{n}^{r}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U{}_{n}^{r}}</annotation>

</semantics>

</math><img src="./f162cf098f3b6a8822e202dcc2ec8daa080a11d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.001ex; height:2.509ex;" alt="{\displaystyle U{}_{n}^{r}}" loading="lazy"> has <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> elements, and its independent sets consist of all subsets of up to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> of the elements. Uniform matroids may be represented by sets of vectors in <a href="General_position" title="General position">general position</a> in an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy">-dimensional vector space. The field of representation must be large enough for there to exist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> vectors in general position in this vector space, so uniform matroids are F-linear for all but finitely many fields F.<a href="#cite_note-21">[21]</a> The same is true for the <a href="Partition_matroid" title="Partition matroid">partition matroids</a>, the direct sums of the uniform matroids, as the direct sum of any two F-linear matroids is itself F-linear.

A <a href="Graphic_matroid" title="Graphic matroid">graphic matroid</a> is the matroid defined from the edges of an <a href="Undirected_graph" class="mw-redirect" title="Undirected graph">undirected graph</a> by defining a set of edges to be independent if and only if it does not contain a <a href="Cycle_(graph_theory)" title="Cycle (graph theory)">cycle</a>. Every graphic matroid is regular, and thus is F-linear for every field F.<a href="#cite_note-tutte65-8">[8]</a>

The <a href="Rigidity_matroid" title="Rigidity matroid">rigidity matroids</a> describe the <a href="Degrees_of_freedom_(mechanics)" title="Degrees of freedom (mechanics)">degrees of freedom</a> of mechanical linkages formed by rigid bars connected at their ends by flexible hinges. A linkage of this type may be described as a graph, with an edge for each bar and a vertex for each hinge, and for one-dimensional linkages the rigidity matroids are exactly the graphic matroids. Higher-dimensional rigidity matroids may be defined using matrices of <a href="Real_number" title="Real number">real numbers</a> with a structure similar to that of the <a href="Incidence_matrix" title="Incidence matrix">incidence matrix</a> of the underlying graph, and hence are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {R} }</annotation>

</semantics>

</math><img src="./786849c765da7a84dbc3cce43e96aad58a5868dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {R} }" loading="lazy">-linear.<a href="#cite_note-22">[22]</a><a href="#cite_note-23">[23]</a>

Like uniform matroids and partition matroids, the <a href="Gammoid" title="Gammoid">gammoids</a>, matroids representing <a href="Reachability" title="Reachability">reachability</a> in <a href="Directed_graph" title="Directed graph">directed graphs</a>, are linear over every sufficiently large field. More specifically, a gammoid with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> elements may be represented over every field that has at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation>

</semantics>

</math><img src="./8226f30650ee4fe4e640c6d2798127e80e9c160d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}" loading="lazy"> elements.<a href="#cite_note-24">[24]</a>

The <a href="Algebraic_matroid" title="Algebraic matroid">algebraic matroids</a> are matroids defined from sets of elements of a <a href="Field_extension" title="Field extension">field extension</a> using the notion of <a href="Algebraic_independence" title="Algebraic independence">algebraic independence</a>. Every linear matroid is algebraic, and for fields of characteristic zero (such as the real numbers) linear and algebraic matroids coincide, but for other fields there may exist algebraic matroids that are not linear.<a href="#cite_note-25">[25]</a>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFOxley2006" class="citation cs2"><a href="James_Oxley" title="James Oxley">Oxley, James G.</a> (2006), Matroid Theory, Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, p. 8, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780199202508</bdi></cite>. For the rank function, see p. 26.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFWelsh2010" class="citation cs2"><a href="Dominic_Welsh" title="Dominic Welsh">Welsh, D. J. A.</a> (2010), Matroid Theory, Courier Dover Publications, p. 10, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780486474397</bdi></cite>.

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <a href="#CITEREFOxley2006">Oxley (2006)</a>, p. 12.

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <a href="#CITEREFOxley2006">Oxley (2006)</a>, pp. 170–172, 196.

</li>

<li id="cite_note-tutte58-5">^ <a href="#cite_ref-tutte58_5-0">a</a> <a href="#cite_ref-tutte58_5-1">b</a> <a href="#cite_ref-tutte58_5-2">c</a> <cite id="CITEREFTutte1958" class="citation cs2"><a href="W._T._Tutte" title="W. T. Tutte">Tutte, W. T.</a> (1958), "A homotopy theorem for matroids. I, II", <a href="Transactions_of_the_American_Mathematical_Society" title="Transactions of the American Mathematical Society">Transactions of the American Mathematical Society</a>, 88 (1): 144–174, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F1993244">10.2307/1993244</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/1993244">1993244</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0101526">0101526</a></cite>.

</li>

<li id="cite_note-Wh872-6"><a href="#cite_ref-Wh872_6-0">^</a> White (1987) p.2

</li>

<li id="cite_note-Wh8712-7"><a href="#cite_ref-Wh8712_7-0">^</a> White (1987) p.12

</li>

<li id="cite_note-tutte65-8">^ <a href="#cite_ref-tutte65_8-0">a</a> <a href="#cite_ref-tutte65_8-1">b</a> <cite id="CITEREFTutte1965" class="citation cs2">Tutte, W. T. (1965), <a rel="nofollow" class="external text" href="http://cdm16009.contentdm.oclc.org/cdm/ref/collection/p13011coll6/id/66650">"Lectures on matroids"</a>, Journal of Research of the National Bureau of Standards, 69B: 1–47, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.6028%2Fjres.069b.001">10.6028/jres.069b.001</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0179781">0179781</a></cite>.

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFRota1971" class="citation cs2"><a href="Gian-Carlo_Rota" title="Gian-Carlo Rota">Rota, Gian-Carlo</a> (1971), "Combinatorial theory, old and new", Actes du Congrès International des Mathématiciens (Nice, 1970), Tome 3, Paris: Gauthier-Villars, pp. 229–233, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0505646">0505646</a></cite>.

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFBixby1979" class="citation cs2">Bixby, Robert E. (1979), "On Reid's characterization of the ternary matroids", <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory</a>, Series B, 26 (2): 174–204, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0095-8956%2879%2990056-X">10.1016/0095-8956(79)90056-X</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0532587">0532587</a></cite>.

</li>

<li id="cite_note-s79-11"><a href="#cite_ref-s79_11-0">^</a> <cite id="CITEREFSeymour1979" class="citation cs2"><a href="Paul_Seymour_(mathematician)" title="Paul Seymour (mathematician)">Seymour, P. D.</a> (1979), "Matroid representation over GF(3)", <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory</a>, Series B, 26 (2): 159–173, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0095-8956%2879%2990055-8">10.1016/0095-8956(79)90055-8</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0532586">0532586</a></cite>.

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFGeelenGerardsKapoor2000" class="citation cs2"><a href="Jim_Geelen" title="Jim Geelen">Geelen, J. F.</a>; Gerards, A. M. H.; Kapoor, A. (2000), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20100924110912/http://www.math.uwaterloo.ca/~jfgeelen/publications/gf4.pdf">"The excluded minors for GF(4)-representable matroids"</a> (PDF), <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory</a>, Series B, 79 (2): 247–299, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjctb.2000.1963">10.1006/jctb.2000.1963</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1769191">1769191</a>, archived from <a rel="nofollow" class="external text" href="http://www.math.uwaterloo.ca/~jfgeelen/publications/gf4.pdf">the original</a> (PDF) on 2010-09-24</cite>.

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFVámos1978" class="citation cs2">Vámos, P. (1978), "The missing axiom of matroid theory is lost forever", <a href="Journal_of_the_London_Mathematical_Society" class="mw-redirect" title="Journal of the London Mathematical Society">Journal of the London Mathematical Society</a>, Second Series, 18 (3): 403–408, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1112%2Fjlms%2Fs2-18.3.403">10.1112/jlms/s2-18.3.403</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0518224">0518224</a></cite>.

</li>

<li id="cite_note-Wh8718-14"><a href="#cite_ref-Wh8718_14-0">^</a> <cite id="CITEREFWhite1987" class="citation cs2">White, Neil, ed. (1987), <a rel="nofollow" class="external text" href="https://archive.org/details/combinatorialgeo0000unse/page/18">Combinatorial geometries</a>, Encyclopedia of Mathematics and its Applications, vol. 29, Cambridge: <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>, p. <a rel="nofollow" class="external text" href="https://archive.org/details/combinatorialgeo0000unse/page/18">18</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-521-33339-3</bdi>, <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:0626.00007">0626.00007</a></cite>

</li>

<li id="cite_note-Ing71-15"><a href="#cite_ref-Ing71_15-0">^</a> <cite id="CITEREFIngleton1971" class="citation cs2">Ingleton, A.W. (1971), "Representation of matroids", in Welsh, D.J.A. (ed.), Combinatorial mathematics and its applications. Proceedings, Oxford, 1969, Academic Press, pp. 149–167, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-12-743350-3</bdi>, <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:0222.05025">0222.05025</a></cite>

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite id="CITEREFOxleySempleVertiganWhittle2002" class="citation cs2">Oxley, James; Semple, Charles; Vertigan, Dirk; Whittle, Geoff (2002), "Infinite antichains of matroids with characteristic set {p}", Discrete Mathematics, 242 (1–3): 175–185, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0012-365X%2800%2900466-0">10.1016/S0012-365X(00)00466-0</a>, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/10092%2F13245">10092/13245</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1874763">1874763</a></cite>.

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <cite id="CITEREFKahn1982" class="citation cs2">Kahn, Jeff (1982), "Characteristic sets of matroids", Journal of the London Mathematical Society, Second Series, 26 (2): 207–217, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1112%2Fjlms%2Fs2-26.2.207">10.1112/jlms/s2-26.2.207</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0675165">0675165</a>, <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:0468.05020">0468.05020</a></cite>.

</li>

<li id="cite_note-Ox225-18"><a href="#cite_ref-Ox225_18-0">^</a> <a href="#CITEREFOxley2006">Oxley (2006)</a>, p. 225.

</li>

<li id="cite_note-Ox226-19"><a href="#cite_ref-Ox226_19-0">^</a> <a href="#CITEREFOxley2006">Oxley (2006)</a>, p. 226.

</li>

<li id="cite_note-Ox228-20"><a href="#cite_ref-Ox228_20-0">^</a> <a href="#CITEREFOxley2006">Oxley (2006)</a>, p. 228.

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <a href="#CITEREFOxley2006">Oxley (2006)</a>, p. 100.

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <cite id="CITEREFGraver1991" class="citation cs2">Graver, Jack E. (1991), "Rigidity matroids", SIAM Journal on Discrete Mathematics, 4 (3): 355–368, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0404032">10.1137/0404032</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1105942">1105942</a></cite>.

</li>

<li id="cite_note-23"><a href="#cite_ref-23">^</a> <cite id="CITEREFWhiteley1996" class="citation cs2"><a href="Walter_Whiteley" title="Walter Whiteley">Whiteley, Walter</a> (1996), "Some matroids from discrete applied geometry", Matroid theory (Seattle, WA, 1995), Contemporary Mathematics, vol. 197, Providence, RI: American Mathematical Society, pp. 171–311, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fconm%2F197%2F02540">10.1090/conm/197/02540</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-8218-0508-4</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1411692">1411692</a></cite>.

</li>

<li id="cite_note-24"><a href="#cite_ref-24">^</a> <cite id="CITEREFLindström1973" class="citation cs2">Lindström, Bernt (1973), "On the vector representations of induced matroids", The Bulletin of the London Mathematical Society, 5: 85–90, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1112%2Fblms%2F5.1.85">10.1112/blms/5.1.85</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0335313">0335313</a></cite>.

</li>

<li id="cite_note-25"><a href="#cite_ref-25">^</a> <cite id="CITEREFIngleton1971" class="citation cs2">Ingleton, A. W. (1971), "Representation of matroids", Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), London: Academic Press, pp. 149–167, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0278974">0278974</a></cite>.

</li>

</ol></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-11-09" href="https://en.wikipedia.org/wiki/?title=Matroid_representation&oldid=1256253219">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>